package com.ruben.leetCode;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;

/**
 * @ClassName: FindMinArrowShotsSolution
 * @Description: 我还没有写描述
 * @Date: 2020/11/23 0023 21:34
 * *
 * @author: <achao1441470436@gmail.com>
 * @version: 1.0
 * @since: JDK 1.8
 */
public class FindMinArrowShotsSolution {

    public static void main(String[] args) {
        FindMinArrowShotsSolution solution = new FindMinArrowShotsSolution();
        System.out.println(solution.findMinArrowShots(new int[][]{{10, 16}, {2, 8}, {1, 6}, {7, 12}}));
    }

    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) {
            return 0;
        }
        // 排序
        Arrays.sort(points, Comparator.comparingInt(point -> point[1]));
        // 最优解覆盖坐标
        int pos = points[0][1];
        // 箭数
        int ans = 1;
        for (int[] balloon : points) {
            // 遍历所有气球
            if (balloon[0] > pos) {
                // 如果当前气球左坐标大于最优解覆盖坐标，说明覆盖的气球又多了一个
                // 最优解置为当前气球右坐标
                pos = balloon[1];
                // 箭数加一
                ++ans;
            }
        }
        return ans;
    }
}
